public class ValidParentheses {

	public boolean isValid(String s) {
		int n = s.length();
		char[] stack = new char[n];
		int top = -1;
		for (int i = 0; i < n; ++i) {
			if (s.charAt(i) == '{' || s.charAt(i) == '[' || s.charAt(i) == '(') {
				stack[++top] = s.charAt(i);
			} else {
				if (top == -1 || s.charAt(i) == '}' && stack[top] != '{'
						|| s.charAt(i) == ']' && stack[top] != '['
						|| s.charAt(i) == ')' && stack[top] != '(')
					return false;
				--top;
			}
		}
		return top == -1;
	}

	public static void main(String[] args) {

	}

}
